package hard;
/**
 * 4.寻找两个正序数组中的中位数
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 *
 * 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 *
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * */
public class MedianSortedArrays {
    // 合并数组求中位数 时间复杂度 ： O(n) 空间复杂度:O(n) n为两个数组总长度
    public double find(int nums1[], int nums2[]){
        int totalLength = nums1.length + nums2.length;
        int tempLength = totalLength;
        int[] resultNums = new int[totalLength];
        double r = 0;
        int i = nums1.length - 1;
        int j = nums2.length - 1;
        while(i >= 0 && j >= 0){
            if(nums1[i] >= nums2[j]){
                resultNums[--tempLength] = nums1[i];
                i--;
            }else{
                resultNums[--tempLength] = nums2[j];
                j--;
            }
        }
        while(i >= 0){
            resultNums[--tempLength] = nums1[i];
            i--;
        }
        while(j >= 0){
            resultNums[--tempLength] = nums2[j];
            j--;
        }
        if(resultNums.length % 2 == 0){
            r = (resultNums[totalLength/2 - 1] + resultNums[totalLength/2]) / 2.0;
        }else{
            r = resultNums[totalLength/2];
        }
        return r;
    }

    // 二分查找 找第k小的数字 时间复杂度 O(log(m+n)) 空间复杂度 O(1)
    public double find1(int nums1[], int nums2[]){
        int totalLength = nums1.length + nums2.length;
        int k = totalLength / 2;
        // 根据两数组长度之和的奇偶性分别进行求解
        if(totalLength % 2 == 1){
            return findKth(nums1, nums2, k + 1);
        }else{
            return (findKth(nums1, nums2, k) + findKth(nums1, nums2, k + 1)) * 0.5;
        }

    }

    // 找第k小数
    public int findKth(int[] nums1, int nums2[], int k){
        int i = 0, j = 0;
        while (true) {
            // 边界情况
            if(i == nums1.length){ //当nums1已经到末尾了，直接返回nums2的第k位数
                return nums2[j + k - 1];
            }
            if(j == nums2.length){//当nums2已经到末尾了，直接返回nums1的第k位数
                return nums1[i + k - 1];
            }
            if(k == 1){
                return Math.min(nums1[i], nums2[j]);
            }

            // 正常情况
            // 当位置超出数组大小时，取数组的长度作为下标
            int newIndex1 = Math.min(nums1.length, i + (k / 2))-1;
            int newIndex2 = Math.min(nums2.length, j + (k / 2))-1;
            if (nums1[newIndex1] <= nums2[newIndex2]) {
                // 缩小查找范围
                // 如果 A[k/2−1] 或者 B[k/2−1] 越界，那么我们可以选取对应数组中的最后一个元素。
                // 在这种情况下，我们必须根据排除数的个数减少k的值，而不能直接将k减去 k/2。
                k -= (newIndex1 - i + 1);
                i = newIndex1 + 1;
            } else {
                k -= (newIndex2 - j + 1);
                j = newIndex2 + 1;
            }


        }
    }



    // main
    public static void main(String[] args) {
        MedianSortedArrays ms = new MedianSortedArrays();
        double rs = ms.find1(new int[]{1,2}, new int[]{1,2});
        System.out.print(rs);
    }

}
